Field of the Disclosure
This disclosure relates generally to reader-writer locks, and more particularly to systems and methods for implementing reader-writer locks that take advantage of available hardware transactional memory.
Description of the Related Art
In a multiprocessor environment, threads can participate in a mutual exclusion protocol through the use of lock or “mutex” constructs. A mutual exclusion lock can either be in a locked state or an unlocked state, and only one thread can hold or own the lock at any given time. The thread that owns the lock is permitted to enter a critical section of code protected by the lock or otherwise access a shared resource protected by the lock. If a second thread attempts to obtain ownership of a lock while the lock is held by a first thread, the second thread will not be permitted to proceed into the critical section of code (or access the shared resource) until the first thread releases the lock and the second thread successfully claims ownership of the lock.
A list-based queue type lock described by J. M. Mellor-Crummy and M. L. Scott (which is sometimes referred to as the MCS lock) maintains an ordered list of client-provided nodes, which includes one node for each thread that is in the critical section or is waiting to enter. In this mutual exclusion lock algorithm, when invoking a lock procedure, a given thread must pass to the lock procedure an indicator (e.g., a pointer) to a node that is not already being used by any thread (including by the given thread for a different lock), and when invoking an unlock procedure, the thread must pass to the unlock procedure an indicator of the same node that it passed to the corresponding lock procedure. The thread is said to “own” the indicated node from the time the given thread invokes the lock procedure until the thread returns from the corresponding unlock procedure. If a thread inserts its node into an empty list, the thread enters the critical section; otherwise, the thread waits until its node is at the head of the list (i.e., until it is the first node in the list). When leaving the critical section, the thread releases the lock by invoking an unlock procedure that removes its node from the list. Thus, a thread in the critical section always owns the first node in the list.
Reader-writer locks are an important category of locks that help programmers overcome the scalability issues that are common with traditional mutual exclusion locks for workloads that include a significant percentage of read-only critical sections of code. At any given time, a reader-writer lock allows one or more reader threads to own a lock in a read-only mode or just one writer thread to own the lock in a write mode. With reader-writer locks, this permission persists until it is explicitly surrendered using an unlock operation.
As with the MCS lock, a reader-writer lock algorithm described by O. Krieger, M. Stumm, R. Unrau, and J. Hanna (which is referred to herein as the KSUH algorithm) also maintains a queue (e.g., a doubly-linked list) of client-provided nodes (one for each thread that is in the critical section or is waiting to enter it). The KSUH algorithm supports acquiring a reader-writer lock in a read-only mode or in a write mode, and allows a reader thread to enter a critical section provided that all of the nodes ahead of its node in the list are also owned by reader threads. Because readers might not exit the critical section in the same order in which they entered the critical section, the KSUH algorithm allows the removal of nodes owned by readers from within the list. Because nodes can be modified an arbitrarily long time after they have been removed from the list, in the KSUH algorithm, if the memory used for a node has since been reallocated for another purpose, such late updates can lead to arbitrary behavior. Thus, the KSUH algorithm requires clients to store nodes in Type Stable Memory (TSM) and/or to ensure that they are never deallocated or reused for a different purpose.